package easy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Solution_LCP_07 {

    private int count = 0;
    private int end = 0;
    private int k = 0;

    public int numWays(int n, int[][] relation, int k) {
        this.end = n - 1;
        this.k = k;
        this.count = 0;
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] ints : relation) {
            Set<Integer> set = map.getOrDefault(ints[0], new HashSet<>());
            set.add(ints[1]);
            map.put(ints[0], set);
        }
        dps(0, map, 0);
        return count;
    }

    private void dps(int now, Map<Integer, Set<Integer>> map, int path) {
        if (now == end && path == k) {
            count++;
        } else {
            if (path < k) {
                Set<Integer> set = map.get(now);
                if (set != null) {
                    for (Integer next : set) {
                        dps(next, map, path + 1);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution_LCP_07 model = new Solution_LCP_07();
        System.out.println(model.numWays(5, new int[][]{{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}}, 3));
        System.out.println(model.numWays(3, new int[][]{{0, 2}, {2, 1}}, 2));
    }
}
